package com.gxc.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
 */
public class LetterCombinations {

    public List<String> letterCombinations(String digits) {
        if (digits.length()==0) return new ArrayList<>();
        Map<Character, String> rel = new HashMap<>();
        rel.put('2', "abc");
        rel.put('3', "def");
        rel.put('4', "ghi");
        rel.put('5', "jkl");
        rel.put('6', "mno");
        rel.put('7', "pqrs");
        rel.put('8', "tuv");
        rel.put('9', "wxyz");

        List<String> res = new ArrayList<>();
        List<Character> ans = new ArrayList<>();
        handle(0, digits, ans, res, rel);
        return res;
    }

    public void handle(int cur, String digits, List<Character> ans, List<String> res, Map<Character, String> map) {
        if (cur == digits.length()) {
            StringBuffer buffer = new StringBuffer();
            for (Character an : ans) {
                buffer.append(an);
            }
            res.add(buffer.toString());
            return;
        }

        String str = map.get(digits.charAt(cur));
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            ans.add(c);
            handle(cur+1, digits, ans, res, map);
            ans.remove(ans.size() - 1);
        }
    }
}
